#include <iostream>
#include <vector>
using namespace  std;

typedef struct Btree
{
    int data;
    struct Btree * left;
    struct Btree * right;
}Btree;
void printP(vector <int> v)
{
    for(int i=0;i<v.size();++i)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
//递归建树
void createTree(Btree*  & btree)
{
    int num;
    cin>>num;

    //输入num如果不是-1 开辟空间存入data 递归给左右子树赋值  否则赋值为NULL并返回
    if(num!=-1)
    {
        //error 当前的btree直接开辟而不是新建一个变量
       // Btree* btree=new Btree;

       //先为节点分配空间然后再存放
        btree=(Btree*)malloc(sizeof(Btree));
        btree->data=num;
        btree->left=NULL;
        btree->right=NULL;
        createTree(btree->left);
        createTree(btree->right);

    } else{
        btree=NULL;
        return ;
    }

}
void preorder(Btree*  btree)
{
    if(btree==NULL)
        return;
    cout<<btree->data;
    preorder(btree->left);
    preorder(btree->right);
}
void searchForPath(Btree*  btree,int sum,vector<int>& v)
{
   if(btree==NULL)
       return ;
   sum-=btree->data;
    v.push_back(btree->data);
    //如果节点的左右子树都是空
   if(sum==0&&btree->left==NULL&&btree->right==NULL)
   {
       printP(v);
       //打印完回朔  回朔一定要return
       v.pop_back();
       return;
   }
   searchForPath(btree->left,sum,v);
   searchForPath(btree->right,sum,v);
   //回朔
   v.pop_back();

}
int main() {

     Btree* btree=NULL;
     vector <int> v;
     createTree(btree);
     searchForPath(btree,22,v);
    return 0;
}
